package com.yulongtian.weekCompetition.month202301.week03;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 可 但超时
 * 树状DP
 *
 * @author yulongTian
 * @create 2023-01-15 13:31
 */
public class Test04 {
    public static void main(String[] args) {
        int n = 6;
        int[][] edges = new int[][]{{0, 1}, {1, 2}, {1, 3}, {3, 4}, {3, 5}};
        int[] price = new int[]{9, 8, 7, 6, 10, 5};
        System.out.println(maxOutput(n, edges, price));
    }

    public static long maxOutput(int n, int[][] edges, int[] price) {
        //构建树  邻接表
        HashMap<Integer, List<Integer>> tree = generateTree(edges);
        long ans = 0L;
        for (int i = 0; i < n; i++) {
            if (tree.get(i).size() != 1) {
                continue;
            }
            int priceByEveryNode = getPriceByEveryNode(price, n, i, tree);
            ans = Math.max(ans, priceByEveryNode);
        }
        return ans;
    }

    //以某一结点为根节点 遍历寻找最大和最小价值  计算并返回开销
    public static int getPriceByEveryNode(int[] price, int n, int node, HashMap<Integer, List<Integer>> tree) {
        boolean[] path = new boolean[n];
        path[node] = true;
        int[] ans = new int[]{price[node], price[node]};
        int nowPrice = price[node];
        dfs(price, path, node, tree, ans, nowPrice);
        return ans[1] - ans[0];
    }

    //dfs
    public static void dfs(int[] price, boolean[] path, int start, HashMap<Integer, List<Integer>> tree, int[] ans, int nowPrice) {

        List<Integer> nexts = tree.get(start);
        for (Integer next : nexts) {
            if (path[next]) {
                continue;
            }
            path[next] = true;
            nowPrice += price[next];
            ans[0] = Math.min(ans[0], nowPrice);
            ans[1] = Math.max(ans[1], nowPrice);
            dfs(price, path, next, tree, ans, nowPrice);
            nowPrice -= price[next];
        }

    }


    //构建树  邻接表
    public static HashMap<Integer, List<Integer>> generateTree(int[][] edges) {
        HashMap<Integer, List<Integer>> tree = new HashMap<>();
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            if (!tree.containsKey(x)) {
                List<Integer> temp = new ArrayList<>();
                temp.add(y);
                tree.put(x, temp);
            } else {
                tree.get(x).add(y);
            }
            if (!tree.containsKey(y)) {
                List<Integer> temp = new ArrayList<>();
                temp.add(x);
                tree.put(y, temp);
            } else {
                tree.get(y).add(x);
            }

        }
        return tree;
    }


}
